The low density parity check (LDPC) code is an error correction code (ECC) used in signal processing. ECC codes are used to detect and correct errors which may be introduced into a signal due to noise or other types of interferences. These errors usually occur as changes to one or more bit values in the signal; that is, the value of one or more bits may change from a “0” to a “1” or the inverse, modifying the information contained in the original signal. Using ECC, the original signal may be substantially reconstructed and the original information contained therein retrieved.
Developed by Robert Gallager in the early 1960's, the use of LDPC codes for error correction has experienced a rise in popularity over the last decade due to its relatively low complexity and increased error correction performance compared to other EECs. This increase in popularity has been further supported by advances in processing device technology which allow LDPC decoders to be readily implemented in small chips, for example, in a dedicated chip such as an ASIC (application specific integrated circuit), as well as in other types of integrated circuits.
LDPC codes may be graphically represented by a Tanner Graph. The Tanner Graph is a bipartite graph with a set of nodes on one side generally referred to as “variable” nodes, and a set of nodes on a second side opposing the variable nodes and generally referred to as “check” nodes. The variable nodes contain information (bits) received in a message which is to be decoded for reconstructing the original message. The check nodes contain parity-check constraints, also known as parity equations, to which the information in the variable nodes is compared for detecting and correcting errors introduced into the received information. The variable nodes and the check nodes are connected by edges, which may be randomly selected, so that one or more variable nodes may connect to one or more check nodes. In a typical Tanner Graph, a variable node will be connected to a plurality of check nodes, and a check node will be connected to a plurality of variable nodes.
Error correction using the Tanner Graph includes use of iterative decoding algorithms. The information received at each variable node is broadcast to all its edge-connected check nodes, and each check nodes responds to each of its edge-connected variable nodes by returning information comparing all the variable node information received (from all the nodes) to the parity-check constraints. This process is generally iterated until convergence, which may be when all the parity-check constraints have been met or when a bit error rate (BER) does not exceed a predetermined value. Iterative decoding algorithms for use with the Tanner Graph are known in the art and therefore no further elaboration is provided herein. Some examples of LDPC decoders and decoder algorithms are described below.
“Low cost LDPC decoder for DVB-S2”, John Dielissen, Andries Hekstra, Vincent Berg; 3-9810801-0-6, Proceedings of the conference on Design, automation and test in Europe: Designers' forum—European Design and Automation Association; Pages 130-135.
“Area-Efficient Min-Sum Decoder Design for High-Rate QC-LDPC Codes in Magnetic Recording”, Hao Zhong, Wei Xu, Nindge Xie, and Tong Zhang; IEEE Transactions On Magnetics, ISSN 0018-9464, Volume 43, Issue 12, Pages 4117-4122.
“Architecture-Aware LDPC Code Design For Multi-Processor Software Defined Radio Systems”, Yuming Zhu, Chaitali Chakrabarti; IEEE Transactions on Signal Processing, Volume 57, Issue 9, Pages 3679-3692.